package sixthweek;

public class SortAlgorithm {

	static <T extends Comparable<? super T>> void swap(T[] data, int i,
                                                       int j) {
		T temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	/**
	 * 选择排序： 选择排序算法通过反复地将某一特定值放到它在列表中的最终已排序位置，从而完成某一列表值的排序。
	 * 选择排序的策略：
	 * 【1】扫描整个列表找到最小值，将这个值与第一个元素交换
	 * 【2】扫描除了有序列表之外的部分无序列表找到最小值，然后将它与无序列表第1个位置上的元素交换
	 * 【3】不断重复【2】一直到无序列表只剩一个元素
	 */
	public static <T extends Comparable<? super T>> void selectionSort(T[] data) {
		long startTime = System.nanoTime();
		int min, time = 0;
		T temp;
		for (int index = 0; index < data.length - 1; index++) {
			min = index;
			for (int scan = index + 1; scan < data.length; scan++) {
				if (data[min].compareTo(data[scan]) > 0) {
					min = scan;
				}
				time++;
			}
			swap(data, min, index);
		}
		long endTime = System.nanoTime();
		System.out.println("选择排序运行时间： " + (endTime - startTime) + "ns\n选择排序排序次数： " + time);
	}

	/**
	 * 插入排序: 通过反复的将某一特定值插入到该列表的某个已经排序的子集中完成对列表值的排序。
	 * 插入排序的策略：
	 * 【1】对列表中的开始的两个值依据其相对大小对其进行排序，如果有必要则将它们互换。
	 * 【2】将列表的第三个值插入到已经有序的列表中的恰当位置
	 * 【3】然后不断的将无序列表的元素一次取出插入到有序列表的合适位置，继续这一个过程最后实现全部有序。
	 */
	public static <T extends Comparable<? super T>> void insertionSort(T[] data) {
		long startTime = System.nanoTime();
		int time = 0;
		for (int index = 1; index < data.length; index++) {
			T key = data[index];
			int position = index;
			/** Shift larger values to the right */
			while (position > 0 && data[position - 1].compareTo(key) > 0) {
				data[position] = data[position - 1];
				position--;
				time++;
			}
			time++;
			data[position] = key;
			time++;
		}
		long endTime = System.nanoTime();
		System.out.println("插入排序运行时间： " + (endTime - startTime) + "ns\n插入排序排序次数： " + time);
	}

	/**
	 * 冒泡排序：通过重复的比较相邻元素且在必要时将它们互换，从而完成对某个列表的排序.
	 * 冒泡排序的策略：
	 * 【1】扫描该列表且比较邻接元素如果他们不是相对顺序排序排列将其互换。这里就是就是将最大值冒泡到列表最后的位置.
	 */
	public static <T extends Comparable<? super T>> void bubbleSort(T[] data) {
		long startTime = System.nanoTime();
		int position, scan, time = 0;
		for (position = data.length - 1; position >= 0; position--) {
			for (scan = 0; scan < position; scan++) {
				if (data[scan].compareTo(data[scan + 1]) > 0) {
					swap(data, scan, scan + 1);
				}
				time++;
			}
		}
		long endTime = System.nanoTime();
		System.out.println("冒泡排序运行时间： " + (endTime - startTime) + "ns\n冒泡排序排序次数： " + time);
	}

	/**
	 * 快速排序：通过将列表分区，然后对这两个分区进行递归式排序，从而完成对整个列表的排序
	 * 快速排序的策略：
	 * 【1】首先，选择一个列表元素作为作为分区元素。
	 * 【2】分割该列表，使得小于该分区元素的所有元素位于该元素的左边，所有大于该分区元素的元素位于右边。
	 * 【3】最后，将该快速排序策略（递归式）应用于两个分区。
	 */
	public static int time;
	public static long startTime1, endTime1;
	public static <T extends Comparable<? super T>> void quickSort(T[] data) {
		quickSortRec(data, 0, data.length - 1);
		System.out.println("快速排序运行时间： " + (endTime1 - startTime1) + "ns\n快速排序排序次数： " + time);
	}
	private static <T extends Comparable<? super T>> void quickSortRec(T[] data, int min, int max) {
		startTime1 = System.nanoTime();
		if (min < max) {
			// create partitions
			int indexofpartition = partition(data, min, max);
			// sort the left partition (lower values)
			quickSortRec(data, min, indexofpartition - 1);
			// sort the right partition (higher values)
			quickSortRec(data, indexofpartition + 1, max);
			time++;
		}
		endTime1 = System.nanoTime();
	}
	private static <T extends Comparable<? super T>> int partition(T[] data, int min, int max) {
		T partitionelement;
		int left, right;
		int middle = (min + max) / 2;

		partitionelement = data[middle];
	    swap(data, middle, min);

	    left = min;
		right = max;
		while (left < right) {
			while (left < right && data[left].compareTo(partitionelement) <= 0) {
				left++;
				time++;
			}
			while (data[right].compareTo(partitionelement) > 0) {
				right--;
				time++;
			}
			if (left < right)
				swap(data, left, right);
		}
		swap(data, min, right);

		return right;
	}

	/**
	 * 归并排序：归并排序是另一种递归排序算法，通过将列表递归式分成两半直至每一个列表都只含有一个元素，
	 * 然后将这些子列表按照顺序重组，这样就完成了对列表的排序。
	 * 归并排序策略：
	 * 【1】首先将该列表分成两个大约相等的部分
	 * 【2】对每一个部分列表递归调用其自身，
	 * 【3】继续该列表的递归分解，直至达到该递归的基本情形，这是该列表被分割成长度为1的列表
	 */
	public static int times;
	public static long startTime2, endTime2;
	public static <T extends Comparable<? super T>> void mergeSort(T[] data, int min, int max){
		startTime2 = System.nanoTime();
		mergesort(data,min,max);
		endTime2 = System.nanoTime();
		System.out.println("归并排序运行时间： " + (endTime2 - startTime2) + "ns\n归并排序排序次数： " + times);
	}
	public static <T extends Comparable<? super T>> void mergesort(T[] data, int min, int max) {
		if (min < max) {
			int mid = (min + max) / 2;
			mergesort(data, min, mid);
			mergesort(data, mid + 1, max);
			merge(data, min, mid, max);
			times++;
		}
	}
	@SuppressWarnings("unchecked")
	private static <T extends Comparable<? super T>> void merge(T[] data, int first, int mid, int last) {
		T[] temp = (T[]) (new Comparable[data.length]);
		int first1 = first, last1 = mid;
		int first2 = mid + 1, last2 = last;
		int index = first1;
		while (first1 <= last1 && first2 <= last2) {
			if (data[first1].compareTo(data[first2]) < 0) {
				temp[index] = data[first1];
				first1++;
			} else {
				temp[index] = data[first2];
				first2++;
			}
			index++;
			times++;
		}
		while (first1 <= last1) {
			temp[index] = data[first1];
			first1++;
			index++;
		}
		while (first2 <= last2) {
			temp[index] = data[first2];
			first2++;
			index++;
		}
		for (index = first; index <= last; index++){
			data[index] = temp[index];
		}
	}
}